// https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

// 算法思路总结：
// 1. 利用数组已排序的特性
// 2. 使用双指针从两端向中间扫描
// 3. 根据和与目标值的大小关系移动指针
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        int n = price.size();

        for (int l = 0, r = n - 1 ; l != r ; )
        {
            int sum = price[l] + price[r];
            if (sum == target)
                return {price[l], price[r]};
            else if (sum > target)
                r--;
            else l++;
        }
        return {};
    }
};

int main()
{
    vector<int> v1 = {3, 9, 12, 15}, v2 = {8, 21, 27, 34, 52, 66};
    int t1 = 18, t2 = 61;
    
    Solution sol;
    auto r1 = sol.twoSum(v1, t1), r2 = sol.twoSum(v2, t2);

    for (const int& num : r1) cout << num << " ";
    cout << endl;

    for (const int& num : r2) cout << num << " ";
    cout << endl;

    return 0;
}